class Solution(object):
    def __init__(self):
        self.max_path_sum = float('-inf')

    def maxPathSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        def maxPathDfs(root):
            if root == None:
                return 0
            lsum = maxPathDfs(root.left)
            rsum = maxPathDfs(root.right)
            a_sum = max(root.val, root.val + lsum + rsum)
            l_sum = root.val + max(0, lsum)
            r_sum = root.val + max(0, rsum)
            self.max_path_sum = max(self.max_path_sum, a_sum, l_sum, r_sum)
            return max(l_sum, r_sum)
        maxPathDfs(root)
            
        return self.max_path_sum
